[洛谷P1880][NOI1995]石子合并

发表于 | 分类于 ， | | 阅读次数:

题目

题目描述

在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。

试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.

输入格式

数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.

输出格式

输出共2行,第1行为最小得分,第2行为最大得分.

样例输入

1
2
4
4 5 9 4

样例输出

1
2
43
54

题解

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<cstdio>
#include<cstring>
#define MAXN 402
using namespace std;
int fmin[MAXN][MAXN];
int sum[MAXN];
int fmax[MAXN][MAXN];
int n;

int main(){
	memset(fmin,0x3f,sizeof(fmin));
	memset(fmax,0,sizeof(fmax));
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int a;
		scanf("%d",&a);
		fmin[i][i]=0;
		fmin[i+n][i+n]=0;
		sum[i]=sum[i-1]+a;
	}
	for(int i=1;i<=n;i++){
		sum[i+n]=sum[n]+sum[i];
	}
	for(int len=2;len<=n;len++){
		for(int i=1;i<=n+n-len+1;i++){
			int j=i+len-1;
			for(int k=i;k<j;k++){
				fmax[i][j]=max(fmax[i][j],fmax[i][k]+fmax[k+1][j]+sum[j]-sum[i-1]);
				fmin[i][j]=min(fmin[i][j],fmin[i][k]+fmin[k+1][j]+sum[j]-sum[i-1]);
			}	
		}
	}
	int minn=1<<30;
	int maxx=0;
	for(int i=1;i<=n;i++){
		minn=min(minn,fmin[i][i+n-1]);
		maxx=max(maxx,fmax[i][i+n-1]);
	}
	printf("%d\n%d",minn,maxx);
	return 0;
}